package 动态规划.递归参数思考型;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/1/28 17:45
 */
public class 买卖股票的最佳时机again {


    /*
     ==================  I   =================
     */

    /*
     这就是 一个简单的贪心问题！
     */
    public int greedy(int[] prices){
        int ans = 0;
        int min = prices[0];
        for(int i = 1;i < prices.length - 1;i++){
            ans = Math.max(ans,prices[i] - min);
            min = Math.min(min,prices[i]);
        }
        return ans;
    }

    /*
     动态规划 的解法：
     这里 只 写 递归 函数，
     至于 ，改 dp（那都是 手到擒来的事情了！）
     f(index，status) 函数的含义，就不分析了！
     直接开写了！
     还要 注意的一个点就是，**不能 当天买，当天卖！**
     */
    public int dpSolution(int index,int status,int[] prices){
        // 走到 末尾 ,直接 返回一个 对结果 不影响判断的 值 就行
        if(index == prices.length){
            return 0;
        }
        int ans = 0;
        int ans1 = 0;
        /*
        status == 0 : 表示 ，当前没 持有股票（可以买股票  ，只能 买一次！）
        status == 1 ： 表示 当前 持有股票（可以 卖出，只能卖 一次！）
        怎么控制  买 卖 一次 ？
        从 买 入手 ？ 有点 不好搞
        但是 从 卖 出入手的话， 就变得简单了，
        直接 在 卖出的时候， 终止 当前 层 递归就行了
         */
        // 当前不 持有股票
        if(status == 0){
            // not buy
            ans = dpSolution(index + 1,status,prices);
            // buy  and pay money
            ans1 = dpSolution(index + 1,1,prices) - prices[index];
        }
        //  当前持有股票
        else{
            // sell, 这里 卖出 当前持有股票的同时， 还 停止了，再向下层递归，从而保证，只能交易一支股票！
            ans = prices[index];
            // not sell
            ans1 = dpSolution(index + 1,0,prices);
        }
        return Math.max(ans,ans1);
    }
    // change to dp
    /*
     可以 进行 空间上的优化， 就是 简单使用几个变量就可以
     因为 依赖关系，只跟  index + 1 有关,不存在 跳跃 依赖！
     */
    public int dp1(int[] prices){
        // 这个 缓存 表， 就不多解释了吧
        int[][] dp = new int[prices.length][2];
        for(int index = prices.length - 1;index >= 0;index--){
            // 内层循环的 范围 很小， 直接 枚举出来， 就行了！ status 就是 0 1 取值
            dp[index][0] = Math.max(dp[index + 1][0],dp[index + 1][1] - prices[index]);
            dp[index][1] = Math.max(prices[index],dp[index + 1][1]);
            /*
             看到下面这种写法 ， 就注意一点，发现 没办法，
             内层 使用for 循环！（状态转移 方程式，在status 的取值。不同的时候的 不一致！）
             */
//            for(int status  = 0;status < 2; status++){
//                dp[index][status] = Math.max();
//            }

        }
        return dp[0][0];
    }
    /*
     优化 空间的 版本，
      这个 代码， 有个手熟悉 就行了
      问到的时候， 知道怎么回事就行了！

      ====
      我都笑了！
      本想 优化空间的， 常数时间 缩少了
      空间消耗 更大了！
      问题 ： 这个 数组的大小，明显 开的 比上面的 dp1 内存要小的 多，但是为什么
      内存消耗 会更大呢？
      感觉 lc 评判机制 是 有问题的！
      告绝纠结于这些东西 也没什么用！

      time ： 4ms
      memory： 59.7M
     */
    public int dp2(int[] prices){
        // 二维 直接 变成 一维 也可以！
        int[][] dp = new int[2][2]; //
        int ans = 0;
        for(int index = prices.length - 1;index >= 0;index--){
            dp[0][0] = Math.max(dp[1][0],dp[1][1] - prices[index]);
            dp[0][1] = Math.max(prices[index],dp[1][1]);
            // 滚动赋值
            ans = Math.max(ans,dp[0][0]);
            dp[1][0] = dp[0][0];
            dp[1][1] = dp[0][1];
        }
        return ans;
    }
    /*
     升级版本： 这样 写的 话 ，来优化 空间， 是 一点 都不会 搞迷的， 非常 推荐这样！
      目前的最优 版本， 根本，就不用数组！
     time : 1ms
     memory: 57.4M
     */
    public int dp3(int[] prices){
//        int[][] dp = new int[2][2]; //
        int pre0 = 0,pre1 = 0,cur0 = 0,cur1 = 0;
        int ans = 0;
        for(int index = prices.length - 1;index >= 0;index--){
            cur0 = Math.max(pre0,pre1 - prices[index]);
            cur1 = Math.max(pre1,prices[index]);
            // 滚动赋值
            pre0 = cur0;
            pre1 = cur1;
        }
        return cur0;
    }

    // =================== II （略）===============================






}